package fun.ticsmyc.question;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-01-30 20:57
 */
public class 小和问题和逆序对 {

    private static int xiaoheSum =0;
    private static int nixuduiSum=0;

    public static void xiaohe(int arr[]){
        if(arr ==null || arr.length<=1){
            return ;
        }
        divide(arr,0,arr.length-1);
    }

    public static void divide(int arr[], int head,int tail){
        if(head == tail){
            return ;
        }
        int mid = (head+tail)/2;
        divide(arr,head,mid);
        divide(arr,mid+1,tail);
        merge(arr,head,tail);
    }

    public static void merge(int arr[],int head,int tail){
        int mid=(head+tail)/2;
        int leftHead =head;
        int rightHead = mid+1;
        int length = tail-head+1;
        int[] temp = new int[length];
        int tempIndex=0;
        while(leftHead<=mid && rightHead<=tail){
            if(arr[leftHead] < arr[rightHead]){
                //小和
                //对于这个arr[rightBegin] ,leftBegin之前的数都比他小，leftBegin之后的数 不一定
                //对于arr[leftBegin] ，rightBegin之后的数都比他小，之前的 一定不小
                xiaoheSum += (tail - rightHead+1);
                temp[tempIndex++] = arr[leftHead++];
            }else if(arr[leftHead] == arr[rightHead]){
                temp[tempIndex++] = arr[rightHead++];
            }else{
                //逆序对
                //arr[leftBegin] > arr[rightBegin]
                //对于这个rightBegin ， leftBegin之后的数都比他大
                nixuduiSum += mid-leftHead+1;
                temp[tempIndex++]=arr[rightHead++];
            }
        }
        while(leftHead <= mid){
            temp[tempIndex++]=arr[leftHead++];

        }
        while(rightHead<=tail){
            temp[tempIndex++]=arr[rightHead++];
        }

        for(int i=0;i<tempIndex;i++){
            arr[i+head] = temp[i];
        }
        //此时，这个局部以mid为分界，右边元素恒大于左边。
    }

    @Test
    public void test(){
        int[] arr = new int[]{364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
        xiaohe(arr);
        ArrayTools.printArray(arr);
        System.out.println(xiaoheSum);
        System.out.println(nixuduiSum);
    }
}
